package com.rem.se.my;

import java.util.Arrays;

/**
 * 冒泡
 * 稳定 o(n^2)
 *
 * @author Rem
 * @date 2023-03-08
 */
public class Bubble {

    public static void main(String[] args) {
        int[] data = new int[]{2, 1, 3, 5, 6, 9, 4, 8, 7};


        //bubble_1(data);
        //bubble_2(data);
        //bubble_3(data);
        //bubble_4(data);
        bubble_5(data);


    }

    /**
     * bubble_4 改成for
     *
     * @param data
     */
    private static void bubble_5(int[] data) {
        int n = data.length - 1;
        while (true) {
            int last = 0;
            for (int j = 0; j < n; j++) {
                if (data[j] > data[j + 1]) {
                    swap(j, j + 1, data);
                    last = j;
                }
                System.out.println(Arrays.toString(data));
            }
            n = last;
            if (n == 0) {
                break;
            }
            System.out.println("冒泡次数" + "");
        }

    }

    /**
     * 排序过一遍后确定下次最大排序次数
     *
     * @param data
     */
    private static void bubble_4(int[] data) {
        int n = data.length - 1;
        for (int i = 0; i < data.length - 1; i++) {
            //一次冒泡需要冒泡次数
            int last = 0;
            for (int j = 0; j < n; j++) {
                if (data[j] > data[j + 1]) {
                    swap(j, j + 1, data);
                    last = j;
                    System.out.println(Arrays.toString(data));
                }
            }
            n = last;
            if (n == 0) {
                break;
            }
            System.out.println("冒泡次数" + i);
        }
    }


    /**
     * 后面顺序确定了 不需要再比较了
     *
     * @param data
     */
    private static void bubble_3(int[] data) {

        //冒泡需要排序的次数=数据量-1
        for (int i = 0; i < data.length - 1; i++) {
            //是否交换过
            boolean flag = false;
            //一次冒泡需要冒泡次数
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    flag = true;
                    swap(j, j + 1, data);
                    System.out.println(Arrays.toString(data));
                }
            }
            if (!flag) {
                break;
            }
            System.out.println("冒泡次数" + i);
        }
    }

    /**
     * 第二次比较 虽然比较次数较bubble_1 减少 但是已经比较好了后面还是会继续比较
     *
     * @param data
     */
    private static void bubble_2(int[] data) {
        //冒泡需要排序的次数=数据量-1
        for (int i = 0; i < data.length - 1; i++) {
            //一次冒泡需要冒泡次数
            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    swap(j, j + 1, data);
                    System.out.println(Arrays.toString(data));
                }
            }
            System.out.println("冒泡次数" + i);
        }
    }

    /**
     * 第二次比较 比较过的数据会重复比较
     *
     * @param data
     */
    private static void bubble_1(int[] data) {
        //冒泡需要排序的次数=数据量-1
        for (int i = 0; i < data.length - 1; i++) {
            //一次冒泡需要冒泡次数
            for (int j = 0; j < data.length - 1; j++) {
                if (data[j] > data[j + 1]) {
                    swap(j, j + 1, data);
                    System.out.println(Arrays.toString(data));
                }
            }
            System.out.println("冒泡次数" + i);
        }
    }

    private static void swap(int i, int j, int[] data) {
        int t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

}
